// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

type Node struct {
	x   int
	y   int
	dis int
}

func shortestPath(grid [][]int) int {
	n := len(grid)

	//处理特殊情况
	if grid[0][0] == 1 || grid[n-1][n-1] == 1 {
		return -1
	}
	if n == 1 && grid[0][0] == 0 {
		return 1
	}

	//定义8个连接方向
	directions := [8][2]int{{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}}

	//BFS队列定义
	queue := make([]Node, 0)

	//追加起始节点
	node := Node{0, 0, 1}
	queue = append(queue, node)
	grid[0][0] = 1

	//BFS过程
	for len(queue) > 0 {
		l := len(queue)
		for i := 0; i < l; i++ {
			cur := queue[0]
			queue = queue[1:]
			//迭代8个方向
			for j := 0; j < len(directions); j++ {
				node := Node{}
				node.x = cur.x + directions[j][0]
				node.y = cur.y + directions[j][1]
				node.dis = cur.dis + 1

				//返回到达目的地后的距离
				if node.x == n-1 && node.y == n-1 {
					return node.dis
				}

				//将有效的连接节点追加到队列中
				if node.x >= 0 && node.x < n && node.y >= 0 && node.y < n && grid[node.x][node.y] == 0 {
					queue = append(queue, node)
					grid[node.x][node.y] = 1 //使用网格值表示访问过的节点
				}
			}
		}
	}
	return -1
}

func main() {
	grid := [][]int{{0, 1}, {1, 0}}
	res := shortestPath(grid)
	fmt.Println(res)
}

//$ go run interview5-6.go
//2
